package 我的Java学习_算法基础.day_03;

import java.util.Random;

import static 我的Java学习_算法基础.day_01.唯一成对的数.printArray;

public class _034_快排之双向扫描分区法 {
    public static void main(String[] args) {
        int[] array = new int[10];
        Random random = new Random();
        for (int i = 0 ;i<array.length;i++){
            array[i]= random.nextInt(20);
        }
        printArray(array);
        quickSort2(array,0,array.length-1);
        printArray(array);
    }
    public static void quickSort2(int[] array,int p,int r){
        if(p<r){
            int q = partition2(array,p,r);
            quickSort2(array,p,q-1);
            quickSort2(array,q+1,r);
        }
    }
    public static int partition2(int[] array,int p,int r){
        int pivot = array[p];
        int left = p+1;
        int right = r;
        while(left<=right){
            while(left<=right&&array[left]<=pivot){
                left++;
            }
            while(left<=right&&array[right]>pivot){
                right--;
            }
            if(left<right){
                int a = array[left];
                array[left] = array[right];
                array[right]=a;
            }
        }
        int a = array[p];           //最后，基元与右侧指针指向元素交换
        array[p]=array[right];
        array[right]=a;
        return right;
    }
}
